﻿#define _CRT_SECURE_NO_WARNINGS 1

////杨辉三角
//class Solution {
//public:
//    vector<vector<int>> generate(int numRows)
//    {
//        vector<vector<int>> v(numRows);
//
//        for (int i = 1; i <= numRows; i++)
//        {
//            v[i - 1].resize(i, 1);
//        }
//
//        for (int i = 2; i < v.size(); i++)
//        {
//            for (int j = 1; j < v[i].size() - 1; j++)
//            {
//                v[i][j] = v[i - 1][j] + v[i - 1][j - 1];
//            }
//        }
//        return v;
//    }
//};
////删除有序数组中的重复项
//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums)
//    {
//        // 双指针
//        int prev = 0;
//        int curr = 1;
//
//        int count = 1;
//
//        while (curr < nums.size())
//        {
//            if (nums[prev] != nums[curr])
//            {
//                nums[++prev] = nums[curr];
//                count++;
//            }
//            curr++;
//        }
//        return count;
//    }
//};
////数组中出现次数超过一半的数字
//class Solution {
//public:
//    int MoreThanHalfNum_Solution(vector<int> numbers)
//    {
//        // 时间复杂度O(N)，空间复杂度O(N)。
//        map<int, int> mapCount;
//
//        vector<int>::iterator it = numbers.begin();
//
//        while (it != numbers.end())
//        {
//            mapCount[*it]++;
//            it++;
//        }
//
//        it = numbers.begin();
//        while (it != numbers.end())
//        {
//            if (mapCount[*it] > (numbers.size() / 2))
//            {
//                return *it;
//            }
//            it++;
//        }
//        return 0;
//    }
//};
//class Solution {
//public:
//    int MoreThanHalfNum_Solution(vector<int> numbers)
//    {
//        // 时间复杂度O(N*logN)，空间复杂度O(1).
//        sort(numbers.begin(), numbers.end());
//
//        return numbers[numbers.size() / 2];
//    }
////};
//class Solution {
//public:
//    int MoreThanHalfNum_Solution(vector<int> numbers)
//    {
//        // 时间复杂度O(N)，空间复杂度O(1)
//        int repet = numbers[0];
//
//        int count = 1;
//
//        for (size_t i = 1; i < numbers.size(); i++)
//        {
//            if (repet == numbers[i])
//            {
//                count++;
//            }
//            else
//            {
//                count--;
//            }
//
//            if (count == 0)
//            {
//                i++;
//                repet = numbers[i];
//                count = 1;
//            }
//        }
//
//        return repet;
//    }
//};
//给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
//你必须设计并实现线性时间复杂度的算法且不使用额外空间来解决此问题。???
//class Solution {
//public:
//	int singleNumber(vector<int>& nums)
//	{
//		空间复杂度O(N)，时间复杂度O(N)
//		map<int, int> m;
//
//		for (int e : nums)
//		{
//			m[e]++;
//		}
//
//
//		for (int e : nums)
//		{
//			if (m[e] == 1)
//			{
//				return e;
//			}
//		}
//		return 0;
//	}
//};
////计算哈夫曼树的代权路径长度
//#include <iostream>
//#include <vector>
//#include <queue>
//#include <algorithm>
//using namespace std;
//
//namespace YX
//{
//	template<typename W>
//	struct BinaryTreeNode
//	{
//		typedef struct BinaryTreeNode<W> Node;
//		Node* _left;
//		Node* _right;
//		W _w;
//
//		BinaryTreeNode(const W& w)
//			:_left(nullptr)
//			, _right(nullptr)
//			, _w(w)
//		{
//
//		}
//
//		bool operator>(const Node& n) const
//		{
//			return this->_w > n._w;
//		}
//
//	};
//
//	template<typename T>
//	struct greater
//	{
//		bool operator()(const T& x, const T& y)
//		{
//			return x > y;
//		}
//	};
//
//	template<>
//	struct greater<BinaryTreeNode<int>*>
//	{
//		bool operator()(const BinaryTreeNode<int>* x, const BinaryTreeNode<int>* y)
//		{
//			return *x > *y;
//		}
//	};
//
//	template<typename T>
//	int WPL(YX::BinaryTreeNode<T>* root, int Depth)
//	{
//		if (root == nullptr)
//		{
//			return 0;
//		}
//
//		if (root->_left == nullptr && root->_right == nullptr)
//		{
//			return root->_w * Depth;
//		}
//
//		return WPL(root->_left, Depth + 1) + WPL(root->_right, Depth + 1);
//	}
//
//};
//
//int main()
//{
//	int arr[] = { 2,4,5,7 };
//
//	priority_queue<YX::BinaryTreeNode<int>*, vector<YX::BinaryTreeNode<int>*>,YX::greater<YX::BinaryTreeNode<int>*>> pq;
//
//	for (auto e : arr)
//	{
//		pq.push(new YX::BinaryTreeNode<int>(e));
//	}
//
//	while (pq.size() != 1)
//	{
//		auto top1 = pq.top();
//		pq.pop();
//		auto top2 = pq.top();
//		pq.pop();
//		YX::BinaryTreeNode<int>* newNode = new YX::BinaryTreeNode<int>(top1->_w+top2->_w);
//
//		newNode->_left = top1;
//		newNode->_right = top2;
//
//		pq.push(newNode);
//	}
//
//	cout << YX::WPL(pq.top(), 0) << endl;
//
//	return 0;
//}
